package com.itheima.algorithm.sort;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;

// 桶排序
public class BucketSort {
    public static void main(String[] args) {
        int[] ages = {20, 18, 28, 66, 25, 31, 67, 30}; // 假设人类年龄 1~99
        System.out.println(Arrays.toString(ages));
        sort(ages);
        System.out.println(Arrays.toString(ages));
    }

    /*
        0
        1   18
        2   20 25 28
        3   31
        4
        5
        6   66 67
        7
        8
        9
     */
    public static void sort(int[] ages) {
        // 1. 准备桶

        ArrayList<Integer>[] buckets = new ArrayList[10];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }
        // 2. 放入年龄数据
        for (int age : ages) {
            buckets[age / 10].add(age);
        }
        int k = 0;
        for (ArrayList bucket : buckets) {
            // 3. 排序桶内元素

            // 先将ArrayList转化为Integer数组
            Integer[] arr = (Integer[]) bucket.toArray(new Integer[bucket.size()]);
            // 再将Integer数组转换为Int数组
            int[] intArr = new int[bucket.size()];
            for (int i = 0; i < arr.length; i++) {
                intArr[i] = arr[i].intValue();
            }
            InsertionSort.sort(intArr);
            System.out.println(Arrays.toString(intArr));
            // 4. 把每个桶排序好的内容，依次放入原始数组
            for (int v : intArr) {
                ages[k++] = v;
            }
        }
    }
}